'''
https://leetcode-cn.com/problems/cousins-in-binary-tree/
层次遍历 并且保存父节点信息
当某层出现x 或y时直接比对 x y是否都有父节点 并且不相等(没有父节点表示他不在这一层次)
'''

from collections import deque
from util.TreeHelper import *


class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = deque()
        if root:
            queue.append((root, None))
        parentX = None
        parentY = None

        while queue:
            for _ in range(0, len(queue)):
                root, parent = queue.popleft()
                if root:
                    if root.val == x:
                        parentX = parent
                    if root.val == y:
                        parentY = parent
                    queue.append((root.left, root.val))
                    queue.append((root.right, root.val))
            if parentX != None or parentY != None:
                if not parentX or not parentY:
                    return False
                return parentX != parentY

        return False


if __name__ == "__main__":
    print(Solution().isCousins(genTreeFromStr("[1,2,3,null,4,null,5]"), 5, 4))
    print(Solution().isCousins(genTreeFromStr("[1,2,3,4]"), 3, 4))
